package leetcode每日一题;

/**
 * 1. 问题描述
 *   一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 *   机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 *   问总共有多少条不同的路径？
 *
 * 2. 算法分析
 *      1. 动态规划
 *          我们设二维dp数组 dp[][],其中dp[i][j]的含义：到达位置(i,j)的方式
 *             实际上有题目的含义我们知道到达(i,j)这个点只有两种方式，分别是：
 *                 1. 从(i,j-1) ---> (i,j) 右移动一个单位
 *                 2. 从(i-1,j) ---> (i,j) 下移动一个单位
 *             由此我们可以得到一个动态方程
 *                 dp[i][j] = dp[i-1][j] + dp[i][j-1]
 *
 *      2. 组合学知识
 *
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 不同路径 {
    public static void main(String[] args) {
        System.out.println(uniquePaths2(10, 10));
    }

    /**
     * 动态规划解决
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n]; // 创建dp数组
        for(int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

    /**
     * 组合学知识
     * @param m
     * @param n
     * @return
     */
    public static long uniquePaths2(int m,int n) {
        return fib(m+n-2) / (fib(n-1) * fib(m-1));
    }

    // 计算阶乘
    public static long fib(int n) {
        if (n == 0 || n == 1) {return 1;}
        return fib(n-1) * n;
    }
}
